#include <bits/stdc++.h>
using namespace std;
 

const int MAX = 1000;
int G[MAX][MAX]; // 存储边信息
int bestx[MAX];  // 最优值的割集
int w[MAX];      // 顶点的权
int n, e;        // 顶点数，边数
ifstream in("input.txt");
ofstream out("output.txt");
/*
分析
解向量：（x1,x2,……xn)是一个01序列，其中xi=1表示点xi在割集，0表示不在割集
解空间：完全二叉树，子集树
用node类来表示节点，每个节点含有的元素：当前层 割边数量 剩余边的数量 解向量
优先级：每个节点当前割边数量
如果还没有到叶节点：
①左子节点直接加入优先队列。修改解向量，该左子节点加入后修改割边数量和剩余边数量。
②右子节点需要判断是否需要剪枝：当前割边数+剩余边数>当前最优解时，加入队列。修改解向量，该右子节点加入后修改剩余边数量。
到达叶节点，即求得最优值
代码
*/
// 结点类
class Node {
public:
  int dep; // 当前层
  int cut; // 割边数量
  int e;   // 剩余边的数量
  int *x;  // 解向量

  Node(int d, int c, int ee) {
    x = new int[n + 1];
    dep = d;
    cut = c;
    e = ee;
  }

  // 割边数大的先出队列
  bool operator<(const Node &node) const { return cut < node.cut; }
};

// 存储待解决的结点的优先队列
priority_queue<Node> q;

// 添加结点
void addNode(Node enode, bool isLeft) {
  Node now(enode.dep + 1, enode.cut, enode.e);
  copy(enode.x, enode.x + n + 1, now.x);
  // 是左结点
  if (isLeft) {
    now.x[now.dep] = 1;          // 因为是左节点 标记是割集元素
    for (int j = 1; j <= n; j++) // 统计割边的增量
      if (G[now.dep][j])
        if (now.x[j] == 0) // 如果当前顶点在割集中，但边的另一个顶点不在割集
        {
          now.cut++; // 割边的数量增加
          now.e--;   // 剩余边的数量减少
        } else
          now.cut--; // 否则割边数量减少
  } else             // 右节点
  {
    now.x[now.dep] = 0; // 标记不是割集元素
    now.e--;            // 剩余边的数量减少
  }
  q.push(now); // 加入优先队列
}

int search() {
  // 初始化 ：层0 割边0 剩余边e
  Node enode(0, 0, e);
  for (int j = 1; j <= n; j++)
    enode.x[j] = 0; // 解向量
  int best = 0;
  // 分支限界求解
  while (true) {
    if (enode.dep > n) // 到达叶子节点，如果比当前最优解更优，更新
    {
      if (enode.cut > best) {
        best = enode.cut;
        copy(enode.x, enode.x + n + 1, bestx);
        break;
      }
    } else // 没有到达叶子节点
    {
      addNode(enode, true);           // 加入左子结点
      if (enode.cut + enode.e > best) // 满足约束条件，加入右子结点
        addNode(enode, false);
    }
    if (q.empty())
      break;
    else // 取出队首元素
    {
      enode = q.top();
      q.pop();
    }
  }
  return best;
}

int main() {
  int a, b, i;
  in >> n >> e;
  memset(G, 0, sizeof(G));
  for (i = 1; i <= e; i++) {
    in >> a >> b;
    G[a][b] = G[b][a] = 1;
  }
  out << search() << '\n';
  // for (i = 1; i <= n; i++) {
  //   out << bestx[i];
  //   if (i != n)
  //     out << " ";
  // }
  // out << '\n';
  in.close();
  out.close();
  return 0;
}

/*
7 18
1 4
1 5
1 6
1 7
2 3
2 4
2 5
2 6
2 7
3 4
3 5
3 6
3 7
4 5
4 6
5 6
5 7
6 7
*/

/*
运用算法分析的知识，分析并阐述求解本问题算法的各个模块的时空复杂度。
（1）时间复杂度：T(n)=O(n*2^n)
①首先分析addNode算法，addNode内部需要遍历所有与u相连的边，所以计算频次记为C1n
③
对于maxCut，最坏情况下算法搜索了所有的2n-1个节点，而每一个节点都被addNode处理，记为`C1*n*（2^n-1）`，另外当level>=n，也就是叶子节点的时候，需要更新解向量，共有`2^(n)`个叶子节点，所以计数频次记为C2*2(n)，另外建立堆的过程计数频次记为C3n2^n
④ 综上总的计数频次为C1*n*（2^n-1）+ C2*2^(n-1)+ C3*n*2^n，化简得T（n）=O(n*2^n)
（2）空间复杂度：S(n)=O(n*2^n)
算法的空间开销在于子集树节点的构建，在最坏情况下将会有2^n-1个节点，每个节点的空间开销记为C1+C2n，因此空间复杂度为S(n)=O（2^n-1*（C1+C2*n））=>
S(n)=O(n*2^n)

 * /

 /*
①
对于一个顶点，它可以被加入割集也可不不加入，所以整个解空间构成子集树。每个顶点包含层次level，当前解的割边数量cut，以及剩下的边的数量e
② 以广度优先的方式搜索子集树，用优先队列模拟，优先级定义为当前节点的割边数量
③剪枝：一方便面优先队列可以用优先队列剪枝，另一方面可以用剩下的边数目+当前割边的数目之和与当前最优割边数量比较，仅当前者较大的时候才进行搜索。
④对于一个将要加入的活节点v，找到多有v，使得（u，v）∈G。如果v在割集中，意味着加入u将会使割边减少1，并且，如果v不在割集中则表示割边增加。
⑤ 搜索子集树可以得到最优解。
 */